import java.util.Deque;
import java.util.LinkedList;

/**
 * 20. 有效的括号
 */
public class Solution_20 {
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        char[] charArray = s.toCharArray();
        int len = charArray.length;
        for (int i = 0; i < len; i++) {
            char c = charArray[i];
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char topChar = stack.pop();
                if (c == ')' && topChar != '(') {
                    return false;
                } else if (c == ']' && topChar != '[') {
                    return false;
                } else if (c == '}' && topChar != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Solution_20 solution = new Solution_20();
        String s = "([])[()]{}";
        boolean ans = solution.isValid(s);
        System.out.println(ans);
    }
}
